#include "huisu.hpp"
using namespace std;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

//int totalScore = 0;
//extern double bosscredit;   //boss收益 还未完成
extern vector<vector<GameElement>> maze; //假设直接访问maze

huisu::huisu(int n)
{
    this->n=n;
    this->score=0;
}

void huisu::set_resource(int x,int y,double val){
    Point p;
    p.x = x;
    p.y = y;
    resourceMap[p] = val;
}

const int huisu::getScore(){
    return score;
}


const vector<Point> huisu::getPath(){
    return path;

}

huisu::~huisu() {}


void huisu::visit_trans(vector<vector<bool>> visited_ext) {


    for (int i = 0; i < visited_ext.size(); ++i) {
        for (int j = 0; j < visited_ext[i].size(); ++j) {
            if (visited_ext[i][j]) {
                visited.insert({i, j});
            }
        }
    }}

void huisu::printMazeWithPath(Point currentStep) {
    vector<vector<char>> temp = mazec;

    // 标记所有路径点
    for (auto& p : path) {
        if (temp[p.x][p.y] == ' ') {
            temp[p.x][p.y] = '.';
        }
    }

    // 标记当前位置
    if (inBounds(currentStep.x, currentStep.y)) {
        temp[currentStep.x][currentStep.y] = '*';
    }

    // 打印迷宫
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << temp[i][j] << ' ';
        }
        cout << '\n';
    }
}

bool huisu::inBounds(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n;
}

int huisu::bfs(Point start, Point target) {
    queue<pair<Point, int>> q;
    map<Point, Point> parent;
    set<Point> vis;
    q.push({start, 0});
    vis.insert(start);
    parent[start] = start;
    //qDebug()<<"开始bfs";
    while (!q.empty()) {
        auto [cur, dist] = q.front(); q.pop();
        if (cur.x == target.x && cur.y == target.y) {
            // 改为非递归路径回溯
            vector<Point> fullPath;
            while (!(cur == start)) {
                fullPath.push_back(cur);
                cur = parent[cur];
            }
            reverse(fullPath.begin(), fullPath.end());
            for (const auto& p : fullPath) {
                cout << "(" << p.x << ", " << p.y << ") ";
            }
            // 直接将路径加入 path_to_exit
            //path_to_exit.insert(path_to_exit.end(), fullPath.begin(), fullPath.end());
            return dist;
        }
        for (int i = 0; i < 4; ++i) {
            int nx = cur.x + dx[i], ny = cur.y + dy[i];
            Point next = {nx, ny};
            if (inBounds(nx, ny) && mazec[nx][ny] != '#' && !vis.count(next)) {
                vis.insert(next);
                parent[next] = cur;
                q.push({next, dist + 1});
            }
        }
    }
    return -1;  // 无法到达
}

int huisu::bfs_toexit(Point start, Point target) {
    queue<pair<Point, int>> q;
    map<Point, Point> parent;
    set<Point> vis;
    q.push({start, 0});
    vis.insert(start);
    parent[start] = start;  // 起点的父节点指向自己
    cout<< "开始bfs_to_exit";

    while (!q.empty()) {
        auto [cur, dist] = q.front(); q.pop();

        // 找到目标点，构建路径
        if (cur.x == target.x && cur.y == target.y) {
            vector<Point> fullPath;
            // 从目标点回溯到起点（不包含起点）
            Point cur_node = cur;
            while (!(cur_node == start)) {
                fullPath.push_back(cur_node);
                cur_node = parent[cur_node];  // 沿父节点回溯
            }
            fullPath.push_back(start);  // 加入起点，完成路径
            reverse(fullPath.begin(), fullPath.end());  // 反转得到从起点到目标的顺序

            // 将路径添加到path_to_exit（若需覆盖历史路径，可先清空：path_to_exit.clear()）
            path_to_exit.insert(path_to_exit.end(), fullPath.begin(), fullPath.end());

            // 输出路径（可选调试）
            for (const auto& p : fullPath) {
                cout << "(" << p.x << ", " << p.y << ") ";
            }

            return dist;  // 返回路径长度
        }

        // 遍历四个方向
        for (int i = 0; i < 4; ++i) {
            int nx = cur.x + dx[i], ny = cur.y + dy[i];
            Point next = {nx, ny};
            // 检查是否在迷宫范围内、不是墙且未被访问过
            if (inBounds(nx, ny) && mazec[nx][ny] != '#' && !vis.count(next)) {
                vis.insert(next);
                parent[next] = cur;  // 记录父节点
                q.push({next, dist + 1});
            }
        }
    }

    cout << "结束bfs（无法到达目标）";
    return -1;  // 无法到达目标
}

void huisu::generate_rp(const vector<vector<GameElement>>& maze) {
    int rows = maze.size();
    int cols = maze[0].size();
    mazec.resize(rows, vector<char>(cols));
    n = rows; // 保证后续一致


    for (int i = 0; i < rows; ++i)
        for (int j = 0; j < cols; ++j) {
            Point p = {i, j};
            switch (maze[i][j].type) {
            case MazeElement::WALL:   mazec[i][j] = '#'; break;
            case MazeElement::PATH:   mazec[i][j] = ' '; resourceMap[p] = 0;break;
            case MazeElement::EXIT:   mazec[i][j] = 'E'; exit = p; break;
            case MazeElement::GOLD:   mazec[i][j] = 'G'; resourceMap[p] = 50; break;
            case MazeElement::TRAP:   mazec[i][j] = 'T'; resourceMap[p] = -30; break;
            case MazeElement::LOCKER: mazec[i][j] = 'L'; resourceMap[p] = 2; break; //此处待传值
            case MazeElement::BOSS:   mazec[i][j] = 'B'; resourceMap[p] = 22; break;
            default:                  mazec[i][j] = ' '; break;
            }
        }

}

void huisu::getVisionOptions(Point player) {
    // 首先检查周围九格是否有任何资源（正或负）
    cout<<"startgetvision";
    bool hasAnyResource = false;
    bool twist=false;
    for (int i = -1; i <= 1; ++i) {
        for (int j = -1; j <= 1; ++j) {
            if (i == 0 && j == 0) continue;

            int nx = player.x + i, ny = player.y + j;
            if (inBounds(nx, ny) && resourceMap[{nx, ny}]>0) {
                hasAnyResource = true;
                break;
            }
        }
        if (hasAnyResource) break;
    }
    //qDebug()<<"是否存在资源"<<hasAnyResource;

    //  如果周围九格无任何资源，直接考虑退出
    // if (!hasAnyResource) {
    //     int distToExit = bfs(player, exit);
    //     if (distToExit !=1) {
    //         return;
    //     }
    //     candidates.push_back({exit, 0, distToExit, 0});
    // }

    // 正常处理视野内的点
    for (int i = -1; i <= 1; ++i) {
        for (int j = -1; j <= 1; ++j) {
            if (i == 0 && j == 0) continue;

            int nx = player.x + i, ny = player.y + j;
            Point target = {nx, ny};
            twist=false;

            if (!hasAnyResource&&mazec[nx][ny]!='E') continue;   //此处处理出口
            else if(!hasAnyResource&&mazec[nx][ny]=='E'){
                int exit_dist=bfs(player,exit);
                if(exit_dist==1){
                    candidates.push_back({exit, 0, 1, 0});
                }
                else if(exit_dist==2){
                    Point inter={player.x + i, player.y}; //默认先横向改变
                    candidates.push_back({inter, 0, 1, 0,true,exit});
                    candidates.push_back({exit, 0, 1, 0,true});

                }
                return;
            }
            if (!inBounds(nx, ny)) continue;
            if (mazec[nx][ny] == '#' || visited.count(target)) continue;

            double totalVal = 0.0;
            if (resourceMap.count(target)) {
                totalVal += resourceMap[target];
            }
            // 处理斜角移动时计算两条路径的中间点
            if (abs(i) == 1 && abs(j) == 1) {
                Point inter1 = {player.x + i, player.y};
                Point inter2 = {player.x, player.y + j};

                double valPath1 = 0.0, valPath2 = 0.0;bool path1_wall,path2_wall=0;
                if (inBounds(inter1.x, inter1.y) && resourceMap.count(inter1)&& mazec[inter1.x][inter1.y]!='#') //
                {   valPath1 += resourceMap[inter1];
                    cout<<"inter1资源"<<resourceMap[inter1]<<endl;}
                else if(mazec[inter1.x][inter1.y]=='#'){
                    path1_wall=1;
                    cout<<"(" << inter1.x << ", " << inter1.y << ") "<<"wall"<<mazec[inter1.x][inter1.y]<<endl;
                }
                if (inBounds(inter2.x, inter2.y) && resourceMap.count(inter2)&& mazec[inter2.x][inter2.y]!='#')
                {valPath2 += resourceMap[inter2];
                    cout<<"inter2资源"<<resourceMap[inter2]<<endl;}
                else if(mazec[inter2.x][inter2.y]=='#'){
                    path2_wall=1;
                    cout<<"(" << inter2.x << ", " << inter2.y << ") "<<"wall"<<mazec[inter2.x][inter2.y]<<endl;
                }
                if((valPath1>=valPath2&&!path1_wall)||(valPath1<valPath2&&!path1_wall&&path2_wall)){
                    candidates.push_back({inter1, valPath1, 0, -1,true,target});
                    totalVal += valPath1;
                    cout<<"选择先改变x路径"<<endl;
                    cout<<"走"<<"(" << inter1.x << ", " << inter1.y << ") "<<mazec[inter1.x][inter1.y]<<valPath1<<endl;
                }
                else if((valPath1>=valPath2&&path1_wall&&!path2_wall)||(valPath1<valPath2&&!path2_wall)){
                    candidates.push_back({inter2, valPath2, 0, -1,true,target});
                    totalVal += valPath2;
                    cout<<"选择先改变y路径"<<endl;
                    cout<<"走"<<"(" << inter2.x << ", " << inter2.y << ") "<<mazec[inter2.x][inter2.y]<<valPath2<<endl;
                }
                twist=true;
            }

            int dist = bfs(player, target);
            if (dist > 0 && totalVal >= 0.0) {
                double valueRate = totalVal / dist;
                candidates.push_back({target, totalVal, dist, valueRate,twist});
                cout<<"走到目标点"<<target.x<<","<<target.y<<"获得资源"<<totalVal<<endl;
            }
        }
    }
    cout<<"over";
}

void huisu::after_greedy_findexit(Point current){
    Point next;int j=0;int dist_to_exit;
    cout<<path_to_exit.size()<<" "<<"wowowo";
    // for (const auto& p : path_to_exit) {
    //     cout << "(" << p.x << ", " << p.y << ") ";
    // }
    dist_to_exit=bfs_toexit(current,exit);  //每次bfs更新
    for (const auto& p : path_to_exit) {
        cout << "(" << p.x << ", " << p.y << ") ";
    }
    cout<<path_to_exit.size()<<" "<<j;
    next=path_to_exit[j];
    j++;
    path.push_back(next);
    visited.insert(current);
    getVisionOptions(next);
    while(candidates.empty()){
        next=path_to_exit[j];
        if(next==exit){
            return;
        }
        path.push_back(next);   //会默认将再次开启贪心的坐标放入path两次
        score+=resourceMap[next];
        resourceMap.erase(next);
        visited.insert(current);
        j++;
        getVisionOptions(next);
    }
    greedyCollect(next);

}
void huisu::greedyCollect(Point start) {
    Point current = start;
    path.push_back(current);
    visited.insert(current);
    int looptime=1;
    //score=0;

    while (true) {
        // 检查周围3×3范围内是否有任何资源
        bool hasResource = false;
        candidates.clear();
        for (int i = -1; i <= 1; ++i) {
            for (int j = -1; j <= 1; ++j) {
                if (i == 0 && j == 0) continue;

                Point neighbor = {current.x + i, current.y + j};
                // 确保只有资源大于0的点才算资源
                if (inBounds(neighbor.x, neighbor.y) &&
                    resourceMap[neighbor] > 0 &&
                    !visited.count(neighbor)) {
                    hasResource = true;
                    cout << "ifhasResource1: " << hasResource << endl;
                    break;
                }
            }
            if (hasResource) break;
        }

        // 输出检查结果，确保资源是否存在
        cout << "ifhasResource2: " << hasResource << endl;

        //如果没有资源，直接前往出口
        if (!hasResource) {
            cout << "No resources, heading to exit!" << endl;
            //int distoexit = bfs(current, exit);
            getVisionOptions(current);
            if(!candidates.empty()){
                for(auto p:candidates){
                    if(p.twist_to==exit){
                        path.push_back(p.pos);
                    }
                }
                path.push_back(exit);}
            else if(candidates.empty()){
                after_greedy_findexit(current);
                return;
            }
        }

        // 正常贪心算法流程
        candidates.clear();
        cout << "nowpath:" << endl;
        for (const auto& p : getPath()) {
            cout << "(" << p.x << ", " << p.y << ") "<<endl;
        }
        getVisionOptions(current);
        cout << "nowpath:" << endl;
        for (const auto& p : getPath()) {
            cout << "(" << p.x << ", " << p.y << ") "<<endl;
        }
        cout<<looptime<<"aftergetvision"<<endl;
        if (candidates.empty()||!hasResource) {
            cout << "No valid candidates, breaking!" << endl;  // Debug输出
            return;
        }

        sort(candidates.begin(), candidates.end(), [](const Step& a, const Step& b) {
            return a.valuePerStep > b.valuePerStep;
        });

        Step best = candidates[0];
        score+=candidates[0].score;
        cout<<"资源值加"<<candidates[0].score;

        int dist = bfs(current, best.pos);
        if (dist > 0) {
            vector<Point> bestPath;
            Point cur = best.pos;

            if (best.if_twist) {
                for (auto& it : candidates) {
                    if (it.valuePerStep < 0 && it.twist_to == cur) {
                        bestPath.push_back(it.pos);
                        visited.insert(it.pos);
                        resourceMap.erase(it.pos);
                        //score+=it.score;
                        //cout<<"资源值加"<<it.score;
                    }
                }
            }
            bestPath.push_back(cur);

            path.insert(path.end(), bestPath.begin(), bestPath.end());
            cout << "nowpath:" << endl;
            for (const auto& p : getPath()) {
                cout << "(" << p.x << ", " << p.y << ") ";
            }
            current = best.pos;
            visited.insert(current);
            resourceMap.erase(current);
            cout<<looptime<<"aftergreedy"<<endl;
            looptime++;
            cout<<"nowpos"<<'('<<current.x<<current.y<<')'<<endl;
        }
    }

    printMazeWithPath(current);  // 打印最终路径
}
